package com.lfg.leetcode.leetcode100;


public class No130solve {

    public static void main(String[] args) {
        char[][] board = new char[4][5];//[[],[],[],[]
        board[0] = new char[]{'X', 'O', 'X', 'O', 'X', 'O'};
        board[1] = new char[]{'O', 'X', 'O', 'X', 'O', 'X'};
        board[2] = new char[]{'X', 'O', 'X', 'O', 'X', 'O'};
        board[3] = new char[]{'O', 'X', 'O', 'X', 'O', 'X'};
//        board[4] = new char[]{'X','X','O','X','O'};

        solve(board);
        for (int y = 0; y < board.length; y++) {
            for (int x = 0; x < board[y].length; x++) {
                System.out.print(board[y][x]);
            }
            System.out.println();
        }
    }


    public static void solve(char[][] board) {
        if (board.length == 0) {
            return;
        }

        for (int i = 0; i < board[0].length; i++) {
            BFS(board, 0, i);
            BFS(board, board.length - 1, i);
        }
        for (int j = 0; j < board.length; j++) {
            BFS(board, j, 0);
            BFS(board, j, board[0].length - 1);
        }
        for (int y = 0; y < board.length; y++) {
            for (int x = 0; x < board[y].length; x++) {
                if (board[y][x] == 'O') {
                    board[y][x] = 'X';
                }
            }
        }
        for (int y = 0; y < board.length; y++) {
            for (int x = 0; x < board[y].length; x++) {
                if (board[y][x] == ' ') {
                    board[y][x] = 'O';
                }
            }
        }
    }

    public static void BFS(char[][] board, int x, int y) {
        if (x < 0 || y < 0 || x >= board.length || y >= board[0].length) {
            return;
        }
        if (board[x][y] == ' ' || board[x][y] == 'X') {
            return;
        }

        if (board[x][y] == 'O') {
            board[x][y] = ' ';
        }
        BFS(board, x, y - 1);
        BFS(board, x, y + 1);
        BFS(board, x - 1, y);
        BFS(board, x + 1, y);
    }
}
